package com.leetcode.algorithm.topic;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.Stack;

import com.leetcode.algorithm.common.Node;

/**
 * N叉树相关算法题解
 * 
 * (done)589. N叉树的前序遍历
 * (done)590. N叉树的后序遍历
 * (done)429. N叉树的层序遍历
 * (done)559. N叉树的最大深度
 * @author: jie.deng
 * @time: 2019年3月13日 下午11:27:26
 */
public class TreeSolution {
    /**
     * 589. N叉树的前序遍历
     * 
	 * 给定一个 N 叉树，返回其节点值的前序遍历。
	 * 例如，给定一个 3叉树 :
	 * 返回其前序遍历: [1,3,5,6,2,4]。
	 * 
	 * 说明: 递归法很简单，你可以使用迭代法完成此题吗?
     * @param root
     * @return
     */
	public List<Integer> preorder(Node root) {
		List<Integer> list = new ArrayList<Integer>();
		if (root == null) {
			return list;
		}
		Stack<Node> stack = new Stack<Node>();
		stack.push(root);
		while (!stack.isEmpty()) {
			Node node = stack.pop();
			list.add(node.val);// 遍历当前结点
			List<Node> children = node.children;
			if (children != null) {
				for (int i = children.size() - 1; i >= 0; i--) { // 孩子结点从后往前依次入栈，以确保出栈时的顺序是从前往后
					stack.push(children.get(i));
				}
			}
		}
		return list;
	}

	/**
     * 590. N叉树的后序遍历
     * 
	 * 给定一个 N 叉树，返回其节点值的后序遍历。
	 * 例如，给定一个 3叉树 :
	 * 返回其后序遍历: [5,6,3,2,4,1].
	 * 
	 * 说明: 递归法很简单，你可以使用迭代法完成此题吗?
     * @param root
     * @return
     */
	public List<Integer> postorder(Node root) {
		List<Integer> list = new ArrayList<Integer>();
		if (root == null) {
			return list;
		}
		Node pre = null; // 划重点:记录上次遍历的结点
		Stack<Node> stack = new Stack<Node>();
		stack.push(root);
		while (!stack.isEmpty()) {
			Node cur = stack.peek();
			if (cur.children == null || cur.children.size() == 0 || cur.children.get(cur.children.size() - 1) == pre) {
				// 划重点:如果当前结点没有孩子或者上次遍历的结点为孩子的最后一个，则开始遍历当前结点
				stack.pop();
				list.add(cur.val);// 遍历当前结点
				pre = cur;
			} else {
				// 需要先遍历孩子结点，孩子入栈
				List<Node> children = cur.children;
				if (children != null) {
					for (int i = children.size() - 1; i >= 0; i--) {
						stack.push(children.get(i));
					}
				}
			}
		}
		return list;
	}

	/**
     * 429. N叉树的层序遍历
     * 
     * 给定一个 N 叉树，返回其节点值的层序遍历。 (即从左到右，逐层遍历)。
     * 
     * 例如，给定一个 3叉树 :
     * 返回其层序遍历:
     * [
     *      [1],
     *      [3,2,4],
     *      [5,6]
     * ]
     * 
     * 说明:
     * 树的深度不会超过 1000。
     * 树的节点总数不会超过 5000。
     * @param root
     * @return
     */
	public List<List<Integer>> levelOrder(Node root) {
		List<List<Integer>> list = new ArrayList<List<Integer>>();
		if (root == null) {
			return list;
		}
		Queue<Node> queue = new LinkedList<Node>();
		queue.offer(root);
		while (!queue.isEmpty()) {
			List<Integer> levelList = new ArrayList<Integer>();
			int size = queue.size(); // 当前层次结点个数
			for (int i = 0; i < size; i++) { // 遍历当前层
				Node node = queue.poll();
				levelList.add(node.val); // 遍历当前结点
				List<Node> children = node.children;
				if (children != null) {
					for (Node child : children) {
						queue.offer(child);
					}
				}
			}
			list.add(levelList);
		}
		return list;
	}

	/**
	 * 559. N叉树的最大深度
	 * 
	 * 给定一个 N 叉树，找到其最大深度。
	 * 最大深度是指从根节点到最远叶子节点的最长路径上的节点总数。
	 * 
	 * 例如，给定一个 3叉树 :
	 * 我们应返回其最大深度，3。
	 * 
	 * 说明:
	 * 
	 * 树的深度不会超过 1000。
	 * 树的节点总不会超过 5000。
	 * @param root
	 * @return
	 */
	public int maxDepth(Node root) {
		if (root == null) {
			return 0;
		}
		if (root.children == null) {
			return 1;
		}
		int maxDepth = 0;
		for (Node child : root.children) {
			int depth = maxDepth(child); // 递归
			if (maxDepth < depth) {
				maxDepth = depth;
			}
		}
		return maxDepth + 1;
	}

}